package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @author flutterdash@qq.com
 * @since 2021/7/9 22:07
 */
class P36 : TestDsl {

    private fun isValidSudoku(board: Array<CharArray>): Boolean {
        val size = 9
        val cache = BooleanArray(size + 1)

        fun clearCache() {
            for (i in cache.indices)
                cache[i] = false
        }

        fun getNumber(c: Char): Int = c - '0'
        fun isValid(ch: Char): Boolean {
            return if (ch != '.') {
                val number = getNumber(ch)
                if (!cache[number]) {
                    cache[number] = true
                    true
                } else
                    false
            } else {
                true
            }
        }

        fun isValidRow(row: Int): Boolean {
            for (c in 0 until size) {
                val ch: Char = board[row][c]
                if (!isValid(ch))
                    return false
            }
            return true
        }

        fun isValidColumn(column: Int): Boolean {
            for (r in 0 until size) {
                val ch: Char = board[r][column]
                if (!isValid(ch))
                    return false
            }
            return true
        }

        fun isValidBox(r: Int, c: Int): Boolean {
            for (rPos in r until (r + 3)) {
                for (cPos in c until (c + 3)) {
                    val ch = board[rPos][cPos]
                    if (!isValid(ch))
                        return false
                }
            }
            return true
        }

        for (i in 0 until size) {
            clearCache()
            if (!isValidColumn(i))
                return false
            clearCache()
            if (!isValidRow(i))
                return false
            clearCache()

            val row = if (i < 3) 0 else (i / 3)
            val column = i % 3
            if (!isValidBox(row * 3, column * 3))
                return false
        }

        return true
    }

    @Test
    fun test0() {
        isValidSudoku(
            arrayOf(
                charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
                charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
                charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
            )
        ).log()
    }

    @Test
    fun test1() {
        isValidSudoku(
            arrayOf(
                charArrayOf('.', '2', '1', '.', '.', '.', '.', '.', '.'),
                charArrayOf('.', '.', '.', '.', '6', '.', '.', '.', '.'),
                charArrayOf('.', '.', '.', '.', '.', '.', '7', '.', '.'),
                charArrayOf('.', '.', '.', '.', '5', '.', '.', '.', '.'),
                charArrayOf('.', '.', '5', '.', '.', '.', '.', '.', '.'),
                charArrayOf('.', '.', '.', '.', '.', '.', '3', '.', '.'),
                charArrayOf('.', '.', '.', '.', '.', '.', '.', '.', '.'),
                charArrayOf('3', '.', '.', '.', '8', '.', '1', '.', '.'),
                charArrayOf('.', '.', '.', '.', '.', '.', '.', '.', '8')
            )
        ).log()
    }

}
